import java.util.Arrays;

/**
 * Created with IntelliJ IDEA.
 * Description:
 * user:likai
 * Date:2022-11-02
 * Time:10:26
 */
public class Test {
    public static void swap(int[]array,int start,int end){
        int tmp=array[start];
        array[start]=array[end];
        array[end]=tmp;
    }
    public static void partition(int [] array){
        int mid=part(array,0,array.length-1);
        //左
        part(array,0,mid-1);
        //右
        part(array,mid+1,array.length-1);
    }
    public static int part(int []array,int left,int right){
        int pre=left;
        int cur=left+1;
        int tmp=array[left];
        while(cur<=right){
            //cur是找大的值
            if(array[cur]<tmp){
                //pre是找小的值
                if(array[pre]<=tmp){
                    pre++;
                }
                //交换
                if(pre!=left){
                    swap(array, pre, cur);
                }
            }
            cur++;
        }
        swap(array,left,pre);
        return pre;
    }
    //找中位数
    public static int findMidVal(int []array,int left,int right){
        int mid=(left+right)/2;
        if(array[left]<array[right]){
            if(array[mid]<array[left]){
                return left;
            } else if (array[mid]>array[right]) {
                return right;
            }else {
                return mid;
            }
        }else{
            if(array[mid]>array[left]){
                return left;
            } else if (array[mid]<array[right]) {
                return right;
            }else {
                return mid;
            }
        }
    }
    //归并排序
    public static void mergeSort(int []array){
        merge(array,0,array.length-1);
    }
    public static void merge(int[]array,int left,int right){
        //分解
        if(left==right){
            return;
        }
        int mid=(left+right)/2;
        merge(array,left,mid);
        merge(array,mid+1,right);
        //合并
        mergeChild(array,left,right,mid);
    }
    public static void mergeChild(int []array,int left,int right,int mid){
         int sl=left;
         int el=mid;
         int sr=mid+1;
         int er=right;
         int []tmp=new int[right-left+1];
         int i=0;
         while(sl<=el&&sr<=er){
             if(array[sl]<=array[sr]){
                 tmp[i++]=array[sl++];
             }else{
                 tmp[i++]=array[sr++];
             }
         }
         while(sl<=el){
             tmp[i++]=array[sl++];
         }
         while(sr<=er){
             tmp[i++]=array[sr++];
         }
        for (int j = 0; j < tmp.length; j++) {
            array[j+left]=tmp[j];
        }
    }
    public static void countSort(int[]array){
        int max=array[0];
        int min=array[0];
        //找到最大最小值
        for (int i = 0; i < array.length; i++) {
            if(array[i]>max){
                max=array[i];
            }
            if(array[i]<min){
                min=array[i];
            }
        }
        //建立数组
        int []count=new int[max-min+1];
        //开始计数
        for (int i = 0; i < array.length; i++) {
            count[array[i]-min]++;
        }
        //打印出来
        int sum=0;
        int i=0;
        while(sum<count.length){
            if(count[sum]!=0){
                array[i++]=sum+min;
                count[sum]--;
            }else{
                sum++;
            }
        }
    }

    public static void main(String[] args) {
        int []array={16,37,52,33,21,12,32};
        countSort(array);
        System.out.println(Arrays.toString(array));
    }
}
